Test Series - Data Structure

3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117

Test Number 102/115

Q: Which of the following schemes does quadratic probing come under?
A. rehashing
B. extended hashing
C. separate chaining
D. open addressing
Solution: Quadratic probing comes under open addressing scheme to resolve collisions in hash tables.
Q: Quadratic probing overcomes primary collision.
A. True
B. False
C. 
D. 
Solution: Quadratic probing can overcome primary collision that occurs in linear probing but a secondary collision occurs in quadratic probing.
Q: What kind of deletion is implemented by hashing using open addressing?
A. active deletion
B. standard deletion
C. lazy deletion
D. no deletion
Solution: Standard deletion cannot be performed in an open addressing hash table, because the cells might have caused collision. Hence, the hash tables implement lazy deletion.
Q: In quadratic probing, if the table size is prime, a new element cannot be inserted if the table is half full.
A. True
B. False
C. 
D. 
Solution: In quadratic probing, if the table size is prime, we can insert a new element even though table is exactly half filled. We can’t insert element if table size is more than half filled.
Q: Which of the following is the correct function definition for quadratic probing?
A. F(i)=i2
B. F(i)=i
C. F(i)=i+1
D. F(i)=i2+1
Solution: The function of quadratic probing is defined as F(i)=i2. The function of linear probing is defined as F(i)=i.
Q: How many constraints are to be met to successfully implement quadratic probing?
A. 1
B. 2
C. 3
D. 4
Solution: 2 requirements are to be met with respect to table size. The table size should be a prime number and the table size should not be more than half full.
Q: Which among the following is the best technique to handle collision?
A. Quadratic probing
B. Linear probing
C. Double hashing
D. Separate chaining
Solution: Quadratic probing handles primary collision occurring in the linear probing method. Although secondary collision occurs in quadratic probing, it can be removed by extra multiplications and divisions.
Q:  Which of the following techniques offer better cache performance?
A. Quadratic probing
B. Linear probing
C. Double hashing
D. Rehashing
Solution: Linear probing offers better cache performance than quadratic probing and also it preserves locality of reference.
Q: What is the formula used in quadratic probing?
A. Hash key = key mod table size
B. Hash key=(hash(x)+F(i)) mod table size
C. Hash key=(hash(x)+F(i2)) mod table size
D. H(x) = x mod 17
Solution: Hash key=(hash(x)+F(i2)) mod table size is the formula for quadratic probing. Hash key = (hash(x)+F(i)) mod table size is the formula for linear probing.
Q: For the given hash table, in what location will the element 58 be hashed using quadratic probing?

0	49
1	
2	
3	
4	
5	
6	
7	
8	18
9	89
A. 1
B. 2
C. 7
D. 6
Solution: Initially, 58 collides at position 8. Another collision occurs one cell away. Hence, F(i2)=4. Using quadratic probing formula, the location is obtained as 2.

You Have Score    /10